﻿// Copyright (c) 2005-2017 Poderosa Project, All Rights Reserved.
// This file is a part of the Granados SSH Client Library that is subject to
// the license included in the distributed package.
// You may not use this file except in compliance with the license.

using System;

namespace Granados.PKI {
    /// <summary>
    /// 
    /// </summary>
    /// <exclude/>
    public class PrimeSieve {

        public readonly static byte[] bitCounts = {
            0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,
            2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,
            2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,
            4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,
            2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,
            4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,
            4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,
            6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
        };

        private uint[] table;

        public PrimeSieve(int x) {
            if (x < 4)
                x = 4;

            int len = (x - 3) / (32 * 2);
            table = new uint[len];

            int max = len * 32;
            int stop = (int)Math.Sqrt((double)max) + 1;
            for (int i = 0; i < stop; i++) {
                if ((table[i / 32] & (1 << (i & (32 - 1)))) == 0) {
                    int k = 3 + i * 2;
                    for (int j = i + k; j < max; j += k) {
                        table[j / 32] |= ((uint)1 << (j & (32 - 1)));
                    }
                }
            }
        }

        public uint AvailablePrimes() {
            uint i, bits, w, primes;
            for (i = 0, primes = 2; i < table.Length; i++) {
                w = table[i];
                for (bits = 0; w != 0; w >>= 8)
                    bits += (uint)bitCounts[w & 0xff];
                primes += (32 - bits);
            }
            return primes;
        }

        public uint getNextPrime(uint x) {
            switch (x) {
                /* Trivial cases. */
                case 0:
                    return 2;
                case 1:
                    return 2;
                case 2:
                    return 3;
                /* Cases above 2 are handled with the table. */
                default:
                    uint p = ((x - 3) / 2) + 1;
                    while (true) {
                        if ((p / 32) >= table.Length)
                            return 0;

                        if ((table[p / 32] & (1u << (int)(p & (32 - 1)))) == 0)
                            return p * 2 + 3;
                        p++;
                    }
            }
        }

    }
}
